url = 'https://www.acwing.com/problem/content/851/'

import sys

N = 510
INF = sys.maxsize

n, m = map(int, input().split())

g = [[INF] * N for _ in range(N)]
for i in range(m):
    a, b, c = map(int, input().split())
    g[a][b] = min(g[a][b], c)

dist = [INF] * N
st = [False] * N
dist[1] = 0

for i in range(n - 1):
    t = -1
    for j in range(1, n + 1):
        if not st[j] and (t == -1 or dist[t] > dist[j]):
            t = j

    for j in range(1, n + 1):
        dist[j] = min(dist[j], dist[t] + g[t][j])

    st[t] = True

if dist[n] == INF:
    print(-1)
else:
    print(dist[n])
